package binary_tree.leetcode.medium;

import java.util.List;

/**
 * @author bruin_du
 * @description 替换单词
 * @date 2022/8/18 20:13
 **/
public class OfferII063_ReplaceWords {
    TreeNode root;

    class TreeNode {
        TreeNode[] next;
        boolean isEnd;

        public TreeNode() {
            next = new TreeNode[26];
            isEnd = false;
        }
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        root = new TreeNode();
        for (String str : dictionary) {
            TreeNode cur = root;
            for (int i = 0; i < str.length(); i++) {
                int index = str.charAt(i) - 'a';
                if (cur.next[index] == null) {
                    cur.next[index] = new TreeNode();
                }
                cur = cur.next[index];
            }
            cur.isEnd = true;
        }

        String[] strings = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String str : strings) {
            TreeNode cur = root;
            for (int i = 0; i < str.length(); i++) {
                int index = str.charAt(i) - 'a';
                if (cur.next[index] == null || i == str.length() - 1) {
                    sb.append(str).append(" ");
                    break;
                } else if (cur.next[index].isEnd) {
                    sb.append(str.substring(0, i + 1)).append(" ");
                    break;
                }
                cur = cur.next[index];
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}
